import heapq
import math
from collections import deque, defaultdict

INF = 10 ** 10
WHITE, GRAY, BLACK = 0, 1, 2


class BinaryIndexedTree:
    def __init__(self, n):
        self.n = n
        self.bit = [0] * (n + 1)

    def update(self, i, delta):
        m = i + 1
        while m < self.n + 1:
            self.bit[m] += delta
            m += m & (-m)

    def sum(self, m):
        result = 0
        while m > 0:
            result += self.bit[m]
            m -= m & (-m)
        return result

    def __getitem__(self, i):
        return self.sum(i + 1)

    def __len__(self):
        return self.n


class UnionFindSet:
    def __init__(self, n):
        self.parents = list(range(n))
        self.sizes = [1] * n

    def find(self, x):
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return True  # cycle detected
        if self.sizes[x] < self.sizes[y]:
            x, y = y, x
        self.parents[y] = x
        self.sizes[x] += self.sizes[y]
        return False


class Heap:
    def __init__(self, *, key=lambda x: x, inv_key=lambda x: x):
        self.heap = []
        self.to_remove = []
        self.key = key
        self.inv_key = inv_key

    def peek(self):
        return self.inv_key(self.heap[0])

    def push(self, x):
        heapq.heappush(self.heap, self.key(x))

    def pop(self):
        return self.inv_key(heapq.heappop(self.heap))

    def remove(self, x):
        k = self.key(x)
        if k == self.heap[0]:
            heapq.heappop(self.heap)
            while self.heap and self.to_remove and self.heap[0] == self.to_remove[0]:
                heapq.heappop(self.heap)
                heapq.heappop(self.to_remove)
        else:
            heapq.heappush(self.to_remove, k)

    def __len__(self):
        return len(self.heap) - len(self.to_remove)


class NextUFS:
    def __init__(self, n):
        self.n = n
        self.parents = list(range(n))

    def find(self, x):
        if x == self.n:
            return self.n
        if self.parents[x] != x:
            self.parents[x] = self.find(self.parents[x])
        return self.parents[x]

    def remove_range(self, x, y):
        # remove [x, y], y included
        removed = set()
        x = self.find(x)
        while x <= y:
            removed.add(x)
            self.parents[x] = x + 1
            x = self.find(x)
        return removed


def bfs(n, adj, s, t=None, p=None):
    d = [INF] * n
    d[s] = 0
    q = deque()
    q.append(s)
    while q:
        u = q.popleft()
        if u == t:
            return d
        for v in adj[u]:
            if d[v] == INF:
                d[v] = d[u] + 1
                q.append(v)
                if p is not None:
                    p[v] = u
    return d


def dfs(n, adj, sources):
    colors = [WHITE] * n

    def visit(u):
        colors[u] = GRAY
        for v in adj[u]:
            if colors[v] == GRAY:
                raise RuntimeError('CycleDetected')
            if colors[v] == WHITE:
                visit(v)
        colors[u] = BLACK

    for s in sources:
        if colors[s] == WHITE:
            visit(s)


def dfs_topology_sort(n, adj, indegrees):
    colors = [WHITE] * n
    sources = [v for v in range(n) if indegrees[v] == 0]
    result = []

    def visit(u):
        colors[u] = GRAY
        for v in adj[u]:
            if colors[v] == GRAY:
                raise RuntimeError()
            if colors[v] == WHITE:
                visit(v)
        colors[u] = BLACK
        result.append(u)

    try:
        for s in sources:
            if colors[s] == WHITE:
                visit(s)
        if len(result) != n:
            return None
        result.reverse()
        return result
    except RuntimeError:
        return None


def dijkstra(n, weighted_edges, s, t=None):
    adj = [defaultdict(lambda: INF) for _ in range(n)]
    for u, v, w in weighted_edges:
        adj[u][v] = min(adj[u][v], w)

    d = [INF] * n
    d[s] = 0
    q = [[d[s], s]]
    while q:
        du, u = heapq.heappop(q)
        if du > d[u]:
            continue
        if u == t:
            return d
        for v in adj[u]:
            alt = d[u] + adj[u][v]
            if alt < d[v]:
                d[v] = alt
                heapq.heappush(q, [d[v], v])
    return d


def directed_graph_longest_path(n, weighted_edges):
    adj = [defaultdict(int) for _ in range(n)]
    inv_adj = [defaultdict(int) for _ in range(n)]
    for u, v, w in weighted_edges:
        adj[u][v] = max(adj[u][v], w)
        inv_adj[v][u] = max(inv_adj[v][u], w)

    indegrees = [len(inv_adj[v]) for v in range(n)]
    nodes = dfs_topology_sort(n, adj, indegrees)
    if nodes is None:
        return None
    d = [0] * n
    p = [None] * n
    for v in nodes:
        if len(inv_adj[v]) != 0:
            d[v], p[v] = max((d[u] + adj[u][v], u)
                             for u in inv_adj[v])
    v = max(range(n), key=lambda v: d[v])
    longest_path = []
    while v is not None:
        longest_path.append(v)
        v = p[v]
    longest_path.reverse()
    return longest_path


def undirected_acyclic_graph_longest_path(n, adj):
    d1 = bfs(n, adj, 0)
    u = max(range(n), key=lambda u: d1[u])
    p = [None] * n
    d2 = bfs(n, adj, u, p=p)
    v = max(range(n), key=lambda u: d2[u])
    path = []
    while v is not None:
        path.append(v)
        v = p[v]
    return path


def undirected_graph_find_eulerian_path(n, edges):
    def build():
        adj = [set() for _ in range(n)]
        degrees = [0] * n
        for u, v in edges:
            adj[u].add(v)
            adj[v].add(u)
            degrees[u] += 1
            degrees[v] += 1
        return adj, degrees

    adj, degrees = build()

    def find_source_node():
        ufs = UnionFindSet(n)
        for u in range(n):
            for v in adj[u]:
                ufs.union(u, v)
        is_connected = sum(1 for u in range(n)
                           if u == ufs.parents[u]) == 1
        if not is_connected:
            return None
        is_even = [degree % 2 == 0 for degree in degrees]
        if all(is_even):
            return 0
        if is_even.count(False) == 2:
            return is_even.index(False)
        return None

    s = find_source_node()

    def dfs(s):
        path = []

        def dfs_visit(u):
            while adj[u]:
                v = adj[u].pop()
                adj[v].remove(u)
                dfs_visit(v)
            path.append(u)

        dfs_visit(s)
        path.reverse()
        return path

    path = dfs(s) if s is not None else None
    return path


def directed_graph_find_eulerian_path(n, edges):
    def build():
        adj = [[] for _ in range(n)]
        indegrees = [0] * n
        outdegrees = [0] * n
        for u, v in edges:
            adj[u].append(v)
            outdegrees[u] += 1
            indegrees[v] += 1
        return adj, indegrees, outdegrees

    adj, indegrees, outdegrees = build()

    def find_source_node():
        ufs = UnionFindSet(n)
        for u in range(n):
            for v in adj[u]:
                ufs.union(u, v)
        is_connected = sum(1 for u in range(n)
                           if u == ufs.parents[u]) == 1
        if not is_connected:
            return None
        degrees = [x - y for x, y in
                   zip(indegrees, outdegrees)]
        counter = defaultdict(int)
        for x in degrees:
            counter[x] += 1
        if counter[0] == n:
            return 0
        if (counter[0] == n - 2 and
                counter[-1] == counter[1] == 1):
            return degrees.index(-1)
        return None

    s = find_source_node()

    def dfs(s):
        path = []

        def dfs_visit(u):
            while adj[u]:
                v = adj[u].pop()
                dfs_visit(v)
            path.append(u)

        dfs_visit(s)
        path.reverse()
        return path

    path = dfs(s) if s is not None else None
    return path


def minimum_spanning_tree(n, edges):
    edges = sorted(edges, key=lambda x: x[2])
    mst = []
    ufs = UnionFindSet(n)
    for edge in edges:
        u, v, w = edge
        if ufs.find(u) != ufs.find(v):
            ufs.union(u, v)
            mst.append(edge)
        if len(mst) == n - 1:
            break
    return mst if len(mst) == n - 1 else None


def merge_sort(array):
    if len(array) <= 1:
        return

    half = len(array) // 2
    L = array[:half]
    R = array[half:]
    merge_sort(L)
    merge_sort(R)

    i = j = k = 0
    while i < len(L) and j < len(R):
        if L[i] < R[j]:
            array[k] = L[i]
            i += 1
        else:
            array[k] = R[j]
            j += 1
        k += 1
    while i < len(L):
        array[k] = L[i]
        i += 1
        k += 1
    while j < len(R):
        array[k] = R[j]
        j += 1
        k += 1


def is_prime(n):
    if n <= 1:
        return False
    if n <= 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i = i + 6
    return True


def enumerate_primes(n):
    nums = list(range(2, n + 1))
    i = 0
    while i < len(nums):
        if nums[i] is not None:
            for j in range(i + nums[i], len(nums), nums[i]):
                nums[j] = None
        i += 1
    return [n for n in nums if n is not None]


def prime_factorize(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n = n // 2
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        while n % i == 0:
            factors.append(i)
            n = n // i
    if n > 2:
        factors.append(n)
    return factors


def get_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n) + 1)):
        if n % i == 0:
            divisors.append(i)
            if i * i != n:
                divisors.append(n // i)
    divisors.sort()
    return divisors


class T97Solution:
    """ 双串模板 """
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s1) + len(s2) != len(s3):
            return False
        m, n = len(s1), len(s2)
        dp = [[False for _ in range(n + 1)] for _ in range(m + 1)]  # 注意+1
        dp[0][0] = True  # 先初始化左上角
        for i in range(m + 1):
            for j in range(n + 1):
                if i == 0 and j == 0:
                    continue  # 跳过左上角
                dp[i][j] = (
                        # 从上至下，i == 0的情况，要考虑能不能从空走过来
                        (i != 0 and dp[i - 1][j] and s1[i-1] == s3[i + j - 1])
                        # 可能是and, max, min, sum, prod
                        or
                        # 从左至右，j == 0的情况，要考虑能不能从空走过来
                        (j != 0 and dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
                        # 有时还可能从左上到右下
                )
        return dp[m][n]
